package com.topvision.myviewtest.algorithm.sort;

/**
 * @FileName : SelectionSort.java
 * @Author : Zero_Tzz
 * @E-mail : 497847377@qq.com
 * @Data : 2018-06-30 22:28
 * @Describe : 插入排序O(n^2)
 */
public class InsertSort extends BaseSort {

    /**
     * 普通插入排序方案(交换位置方案)
     *
     * @return
     */
    public static Integer[] sort1() {
        Integer[] arr = generateRandomArray();
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            // 寻找元素arr[i]合适得到位置
            for (int j = i; j > 0; j--) {
                // 第i位置依次往前比较，直到不小于前一个位置为止，此时位置刚好准确
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
        return arr;
    }

    /**
     * 优化插入排序方案(直接赋值方案)
     *
     * @return
     */
    public static Integer[] sort() {
        Integer[] arr = generateRandomArray();
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            // 寻找元素arr[i]合适得到位置

            // step1:拷贝一份当前位置值
            int temp = arr[i];
            int j;
            for (j = i; j > 0; j--) {
                // step2:temp一直往前比较前一个值，直到前一个值不大于该temp值，如果大于temp，则赋值
                if (arr[j - 1] > temp) {
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            arr[j] = temp;

        }
        return arr;
    }
}
